package newBee.class1;

import common.ArrayUtils;

/**
 * https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/description/
 *
 * 商品折扣后的最终价格
 * 解题思路：
 * 大压小单调栈，找到最近一个较小值，相减
 */
public class Code09_finalPrices {
    public static void main(String[] args) {
        int[] arr = {8, 4, 6, 2, 3};
        int[] ans = finalPrices(arr);

        ArrayUtils.printArr(ans);

    }

    public static int[] finalPrices(int[] arr) {
        int n = arr.length, r = 0;
        int[] stack = new int[n];

        for (int i = 0; i < n; i++) {
            while (r > 0 && arr[stack[r - 1]] >= arr[i]) {
                int k = stack[--r];
                arr[k] = arr[k] - arr[i];
            }
            stack[r++] = i;
        }
        return arr;
    }
}
